package algorithms.question.class22;

import common.util.MyUtil;

import java.util.PriorityQueue;

/**
 * https://leetcode-cn.com/problems/trapping-rain-water-ii/
 *
 * @author guichang
 * @date 2021/8/27
 */

@SuppressWarnings("all")
public class Code3_接雨水2 {
    // 放最外一圈到小根堆中 PriorityQueue
    // 弹出最小的比较最大值，上下左右入堆的同时结算水量

    public static void main(String[] args) {
        int[][] nums = {
                {3, 3, 3, 3, 3},
                {3, 2, 2, 2, 3},
                {3, 2, 1, 2, 3},
                {3, 2, 2, 2, 3},
                {3, 3, 3, 3, 3}
        };
        MyUtil.printf("{} == {}", trapRainWater(nums), 10);
    }

    public static int trapRainWater(int[][] nums) {
        if (nums == null || nums.length < 3 || nums[0] == null || nums[0].length < 3) {
            return 0;
        }
        int ROW = nums.length;
        int COL = nums[0].length;
        // 小根堆
        PriorityQueue<Info> queue = new PriorityQueue<>((a, b) -> a.v - b.v);
        // 记录是否入堆
        boolean[][] access = new boolean[ROW][COL];
        // 最外围一圈入堆
        // 上下
        for (int i = 0; i < COL; i++) {
            queue.offer(new Info(nums[0][i], 0, i));
            queue.offer(new Info(nums[ROW - 1][i], ROW - 1, i));
            access[0][i] = true;
            access[ROW - 1][i] = true;
        }
        // 左右
        for (int i = 1; i < ROW - 1; i++) {
            queue.offer(new Info(nums[i][0], i, 0));
            queue.offer(new Info(nums[i][COL - 1], i, COL - 1));
            access[i][0] = true;
            access[i][COL - 1] = true;
        }
        int max = 0;
        int res = 0;
        while (!queue.isEmpty()) {
            Info cur = queue.poll(); // 弹出最小值
            max = Math.max(max, cur.v);
            int x = cur.x;
            int y = cur.y;
            // 上
            if (x - 1 >= 0 && !access[x - 1][y]) {
                res += Math.max(0, max - nums[x - 1][y]);
                queue.offer(new Info(nums[x - 1][y], x - 1, y));
                access[x - 1][y] = true;
            }
            // 下
            if (x + 1 < ROW && !access[x + 1][y]) {
                res += Math.max(0, max - nums[x + 1][y]);
                queue.offer(new Info(nums[x + 1][y], x + 1, y));
                access[x + 1][y] = true;
            }
            // 左
            if (y - 1 >= 0 && !access[x][y - 1]) {
                res += Math.max(0, max - nums[x][y - 1]);
                queue.offer(new Info(nums[x][y - 1], x, y - 1));
                access[x][y - 1] = true;
            }
            // 右
            if (y + 1 < COL && !access[x][y + 1]) {
                res += Math.max(0, max - nums[x][y + 1]);
                queue.offer(new Info(nums[x][y + 1], x, y + 1));
                access[x][y + 1] = true;
            }
        }
        return res;
    }

    private static class Info {
        int v; // 值
        int x; // 横坐标
        int y; // 纵坐标

        public Info(int v, int x, int y) {
            this.v = v;
            this.x = x;
            this.y = y;
        }
    }
}